The present invention relates to data processing systems and, more particularly, to cache memories used in data processing systems.
Cache memories are frequently used in data processing systems in order to increase the speed of such systems. A cache memory is essentially a data buffer or fast memory that quickly provides data in response to memory address signals. The cache memory generally resides within a processor and acts as an intermediate storage between the main memory of the system and the processing elements of the processor.
A processor often has its processing speed affected by the time that it takes to fetch data or instructions from the main memory. With a fast cache memory within the processor storing the most recently used data from main memory, the processor will, in most circumstances, be able to quickly get its needed data and instructions from the cache memory. In addition, since the cache memory resides within the processor, the data and instructions in the cache memory can be provided much more quickly than they could if they needed to be fetched along a bus from main memory.
There are a number of conditions that affect the likelihood of data being in the cache memory when needed by the processor. Data blocks that include words that have been recently used by the processor are much more likely to be needed by the processor than other blocks of data in the main memory. Accordingly, a least recently used (LRU) algorithm is often implemented in the processor for controlling the transfer of the blocks of data between the cache memory and the main memory. The LRU algorithm assures that only the most frequently used blocks of data are stored in the cache memory, and, if a block of data is needed that is not in the cache memory, the needed block replaces a block in the cache memory that is the least recently used. Even with the use of LRU algorithms, however, there are still some instances during the operation of the processor when the processor must wait for data from the main memory because of the need for a block of data not stored in the cache memory. This condition or circumstance is referred to as a "miss". During any given period of time, the number of "misses" in relation to the total number of cache memory accesses is referred to as the "hit ratio".
The type of task being performed also affects the likelihood of data being in the cache memory. For example, if the task involves the use of small clusters of data that are widely spread throughout the main memory, the processor may frequently have to access the main memory as each small cluster of data is needed.
Given these conditions, it is necessary that a data processing system have a cache memory that experiences a maximum hit ratio so that the processor in the system operates with maximum speed and efficiency.